package top.fengleifeng.question;

import top.fengleifeng.util.Constants;
import top.fengleifeng.util.ListNode;

/**
 * @program: leetcode-test
 * @description:
 * @author: fengleifeng
 * @create: 2020-10-12 11:48
 **/
public class Num19删除链表的倒数第N个节点 {

    /**
     * Definition for singly-linked list.
     * public class ListNode {
     * int val;
     * ListNode next;
     * ListNode() {}
     * ListNode(int val) { this.val = val; }
     * ListNode(int val, ListNode next) { this.val = val; this.next = next; }
     * }
     */
    class Solution {
        public ListNode removeNthFromEnd1(ListNode head, int n) {
            if (head == null) {
                return null;
            }
            ListNode temp = head;
            int count = 0;
            while (temp != null) {
                count++;
                temp = temp.next;
            }
            int need = count - n + 1;

            if (need == 1 ) {
                return head.next;
            }
            int tempCount =1;
            temp = head.next;
            ListNode tempPre = head;
            while (temp != null) {
                tempCount++;
                if (tempCount == need) {
                    tempPre.next = temp.next;
                    return head;
                }
                tempPre = temp;
                temp = temp.next;
            }
            return null;
        }

        /**
         * 双指针偏移
         * @param head
         * @param n
         * @return
         */
        public ListNode removeNthFromEnd(ListNode head, int n) {
            ListNode top = new ListNode(0);
            top.next = head;
            ListNode first = top;
            ListNode second = top;
            for (int i = 0; i <= n; i++) {
                second = second.next;
            }
            //
            while (second!=null){
                first= first.next;
                second = second.next;
            }
            first.next = first.next.next;
            return top.next;
        }
    }

    public static void main(String[] args) {
        ListNode listNode = new ListNode(1);
         listNode.next = new ListNode(2);
//         listNode.next.next = new ListNode(3);
//         listNode.next.next.next = new ListNode(4);
//         listNode.next.next.next.next = new ListNode(5);
        ListNode listNode1 = new Num19删除链表的倒数第N个节点().new Solution().removeNthFromEnd(listNode, 1);
        Constants.printListNode(listNode1);
    }
}
